// 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

// 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

// 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

// 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/evaluate-division
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 看了题解

// 执行用时：
// 0 ms
// , 在所有 C++ 提交中击败了
// 100.00%
// 的用户
// 内存消耗：
// 8.1 MB
// , 在所有 C++ 提交中击败了
// 10.32%
// 的用户

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

class Solution {
public:
    vector<double> res;
    bool Nofind;

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string,int> visited;
        unordered_map<string,vector<pair<string,double>>> g;
        for(int i=0;i<equations.size();i++){
            g[equations[i][0]].push_back(make_pair(equations[i][1],values[i]));
            g[equations[i][1]].push_back(make_pair(equations[i][0],1.0/values[i]));
        }

        // 遍历待求
        for(int i=0;i<queries.size();i++){
            // 字母不存在直接-1.0
            if(g.find(queries[i][0])==g.end()){
                res.push_back(-1.0);
                continue;
            }
            Nofind = true;
            visited[queries[i][0]] = 1;
            dfs(g,visited,queries[i][0],queries[i][1],1.0);
            visited[queries[i][0]] = 0;
            if(Nofind){
                res.push_back(-1.0);
            }
        }
        return res;
    }

    void dfs(unordered_map<string,vector<pair<string,double>>>& g,unordered_map<string,int>& visited,string val,string& target,const double& path){
        if(Nofind==false){
            return;
        }
        if(val == target){
            Nofind = false;
            res.push_back(path);
            return;
        }
        for(int i=0;i<g[val].size();i++){
            if(visited[g[val][i].first]==0){
                visited[g[val][i].first]=1;
                dfs(g,visited,g[val][i].first,target,path*g[val][i].second);
                visited[g[val][i].first]=0;
            }
        }
    }
};